Computing systems often require operations to be carried out in a secure manner. For embedded computing devices and for pervasive systems, security of operation is often crucial. To ensure operations and communications are secure, such systems employ cryptographic methods.
The implementation of such a cryptographic method must itself be secure. However, cryptographic methods are subject to attacks. One type of non-invasive attack on computing devices implementing cryptographic methods is known as a power analysis attack. A power analysis attack involves the monitoring of the power consumption of one or more components of a device while the device executes a cryptographic method.
The data derived from monitoring power consumption of the device, combined with knowledge of the operations being carried out by the device, are used to derive the secret information that is part of the cryptographic method.
One type of power analysis attack is known as a Differential Power Analysis (“DPA”) (see, for example, “Differential Power Analysis” P. Kocher, CRYPTO'99, Lecture Notes in Computer Science, 1666, pp. 388-397, 1999, Springer-Verlag). This approach involves generating a large number of inputs by varying different bits in values to be encoded using the cryptographic method implemented in a device. The DPA attack monitors power consumption at different points in the computing device for each of these varying values and, by statistical analysis the differential data, is able to determine a likely key value for the cryptographic method (the secret information).
It is known to use hardware techniques to implement countermeasures for such power analysis attacks. Such an approach may use smoothing or modification of the power consumption of the device to resist a power analysis attack. For example, see U.S. Pat. No. 6,419,159 to Odinak.
Similarly, countermeasures implemented in software have been developed. U.S. Pat. No. 6,295,606 to Messerges and “Towards Sound Approaches To Counteract Power-Analysis Attacks” (S. Chari, C. S. Jutla, J. R. Rao, P. Rohatgi, CRYPTO'99, Lecture Notes in Computer Science, 1666, pp. 398-412, 1999, Springer-Verlag), describe approaches that implement countermeasures to resist power analysis attacks. However, such software approaches involve overhead costs in performance.
U.S. Pat. No. 6,295,606 (Messerges et al., Sep. 25, 2001) discloses a method for resisting a power analysis attack for a cryptographic method. The cryptographic method includes a key value that is combined with a plaintext value by a bitwise Boolean exclusive or operation. The result is used as input for a function that provides a cipher text output. The cryptographic function is usually implemented as one or more table look-ups. The Messerges method involves a masking step carried out by applying a bitwise Boolean exclusive or operation to the key using a random value (the mask). In the Messerges method the masked key is then exclusive or'd with a plaintext and the result is used as input for a function that has, itself, been modified to provide a masked output that can be unmasked to provide the correct result data. To apply a DPA attack against a device that is using the Messerges method requires a second order DPA: power samples for the random value (mask) and the output of the bitwise Boolean XOR of the masked key and the plaintext are required. Complex mathematical analysis is then required to enable the key value to be determined.
In the approach of Messerges, by masking each key value with a different random mask, the cryptographic function is also required to be modified. This typically results in the regeneration of a large table for each application of the cryptographic function. A large overhead price is borne by the system implementing this approach to avoid or limit DPA attacks.
Another known approach is set out in Chari (see above) and involves splitting the key value. In this approach the key value is to be divided into a number (k) of fragments and the fragments are combined with random bits. The approach requires a kth order DPA to attempt to determine the original key value used. However, the Chari approach requires the plaintext to be exclusive or'd with each of the split key values. The end result is that the processor executing the Chari method will require more power as the repeated running of the cryptographic function will necessitate the dissipation of more energy. In devices such as personal digital assistants, energy consumption is a crucial factor and therefore there are limitations to applying this approach for many types of products.
It is therefore desirable to be able implement a countermeasure that will resist a DPA attack and will not require repeated potentially power-consuming operations.